\section{kNN}
There are two paradigms of recommendation: User-based nearest neighbors and item-based nearest neighbors. The idea of user-based nearest neighbors is to find similar users and suggest items that similar users have liked. This approach is based on the idea that similar users likes similar items.

The other paradigm is the item-based nearest neighbors, which instead of users, looks at the items instead, suggesting similar items for example. 

In this project the user-based nearest neighbour is used because the task is to suggest movies to users. These suggestions are based on the ratings the user has made of other movies. It is then possible to look at users which has rated the same movies similarly and find the movies that these users likes, and suggest them to the first user.

To make a recommendation of an item to a user \emph{X}, it is possible to look at the users which are similar \textit{"near"} to \emph{X}. The idea is that similar users like similar items. Since users might use different weighing when rating items, this has to be accounted for. The problem is that even if two users may like and dislike the same items, the first user might be pessimistic and rate a movie 3 if he likes it, where the second user might rate the same movie 5 if he likes it.

The weighting can be accounted for using the algorithm: 
$w(a,b) = \frac{sim(a,b)}{\Sigma_{b \in N} sim(a,b)}$

The general prediction function is: $pred(a,p) = \overline{r_a}+\Sigma_{b \in N} \; w(a,b)(r_{b,p} - \overline{r_b})$

where:

\begin{itemize}
\item $a$ and $b$ are users
\item $r_{a,p}$ is the rating of user $a$ for item $p$
\item $\overline{r_a}$ is user a's avg. rating
\item $P_a,P_b$ are the set of items, rated by users $a$ and $b$
\item $P = P_a \cap P_b$ is the set of items which are rated by both $a$ and $b$
\end{itemize}

An example of this can be seen on figure \ref{fig:predictexample}.

\figur{1}{predictexample.png}{Example of prediction. Source: Lecture slides.}{fig:predictexample}